#pragma once
#include<iostream>
#include <vector>
#include <assert.h>
using  namespace std;
template<class T>
struct Less
{
	bool operator()(const T& left, const T& right)
	{
		return left < right;
	}

};
template<class T>
struct  Greater
{
	bool operator()(const T& left, const T& right)
	{
		return left > right;
	}
};
 template<class T,class Compare=Greater<T>>
 class Heap
 {
 public:
	 Heap()
	 {}
	 Heap(T* a,size_t size)
	 {
		 assert(a);
		 _a.reserve(size);//改变capacity,不改size     //预先开size个空间，若cap<size,增大cap,否则              不变；   resize:  (1),resize(n),调整容器的长度，若n<size,删除多余元素，否则添加采用值初始化的元素，    （2）resize(n,t) 将元素初始化为t;
		 for (size_t i = 0; i < size;i++)
		 {
			 _a.push_back(a[i]);
		 }
		 for (size_t i = (size-2)/2; i >0;i--)
		 {
			 AdjustDown(i);
		 }
	 }
	 void Push(const T& x)
	 {
		 _a.push_back(x);
		 AdjustUp(_a.size()-1);		 
	 }
	 void Pop()
	 {
		 assert(!_a.empty());
		 swap(_a[0], _a[_a.size() - 1]);
		 _a.pop_back();
		 AdjustDown(0);
	 }
	const T& Top()
	 {
		 assert(!_a.empty());
		 return  _a[0];
	 }
	 bool Empty()
	 {
		 return _a.empty();
	 }
	 size_t  Size()
	 {
		 return _a.size();
	 }
 protected:
	 void AdjustDown(size_t root)
	 {
		 Compare  com;
		 size_t parent = root;
		 size_t  child = root * 2 + 1;    //左孩子
		 while (child<_a.size())
		 {
			 if (child + 1 < _a.size() && com(_a[child+1], _a[child]))   //右孩子存在，比较左右孩子
          {
				 ++child;
          }
			 if (com(_a[child], _a[parent]))//右孩子不存在，比较左孩子和父节点
			 {
				 std::swap(_a[parent], _a[child]);
				 parent = child;             //向下调整
				 child = parent * 2 + 1;
			 }
			 else
				 break;            
		 }
	 }
	 void  AdjustUp(size_t child)
	 {
         while (child>0)  //不是根节点
         {
			 Compare com;
			 size_t  parent = (child - 1) / 2;
			 if (com(_a[child],_a[parent]))
			 {
				 std::swap(_a[parent],_a[child]);
				 child = parent;      //向上调整
			 }
			 else
				 break;
         }
	 }
 private: 
	 vector<T> _a;
 };

 